A filesystem is a means to organize data on a storage device by providing procedures to store, retrieve and update the data, as well as manage the available space on the storage device or devices. A filesystem organizes data in an efficient manner and is tuned to the specific characteristics of the storage device. Filesystems are used on various types of data storage devices, such as hard disk drives, floppy disks, optical discs, or flash memory storage devices, to maintain the physical locations of computer files. Filesystems generally allocate space in a granular manner, usually using multiple physical units on the storage device. The file system is responsible for organizing files and directories, and keeping track of which areas of the device belong to certain files and which are not being used.
The filesystem contains data blocks storing the actual data from an application or operating system running on the computing device, as well as metadata blocks. The metadata contains information about the design, structure and layout of the data structures used to store the actual data. Traditionally, filesystem checkers are used to verify that the metadata contained therein is correct. Conventional filesystem checking has been done in a series of passes over the filesystem, each pass looking for a certain kind of error. Assuming that the filesystem is large enough that the state cannot all be stored in memory, it must be reread from the disk on each pass. In addition, not all passes read the data from the disk in a linear fashion, and sometimes, depending upon the layout of the blocks on disk, it can approach random input/output (I/O) if the filesystem checker has not been designed carefully. As filesystems grow in size, the time taken to check them also grows. For very large datasets, the time taken to check the filesystem can easily reach days or weeks.